The present invention relates to a miss detector for a content addressable memory.
Content addressable memories find wide application for example in cache memories.
In operation, address information, which may truncated, can be stored in the CAM. At a later stage, information is applied to the CAM and where a match occurs between the applied information and the stored information a so-called xe2x80x9chitxe2x80x9d occurs defined by a logic 1 occurring on an output line from the CAM corresponding to the bit position at which the hit occurred.
Where there is no match, no hit occurs, and positive indication of this situation is required.
According to a first aspect of the present invention there is provided a miss detector for a CAM having m output lines, said detector having n pairs of input terminals, wherein the binary equivalent of m has n digits, each input pair comprising a true input terminal and a false input terminal, circuitry connecting each output line either to a true or a false input terminal of every pair, and gating circuitry coupled to each pair, said gating circuitry having an output indicative of a miss on said output lines of said CAM.
According to a second aspect of the present invention there is provided a miss detector for a CAM having m output lines numbered 0 to (mxe2x88x921), the detector having n pairs of input terminals, each pair comprising a true and a false input terminal, each pair corresponding to a bit position in the binary equivalent of m, connecting circuitry connecting each output line to a true or false input terminal of each pair of input terminals in conformity with the binary equivalent of the number of said output lines, index circuitry coupled to the true input terminals of each pair and having an index output corresponding to the binary equivalent of an output line when a hit occurs on said output line, and gating circuitry having inputs coupled to each pair, said gating circuitry having an output indicative of a miss.
Preferably said gating circuitry comprises a two-input OR gate connected to each pair of input terminals.
Advantageously said gating circuitry further comprises an n-input output OR gate having an input from each OR gate output.
Conveniently said connecting circuitry comprises a respective pull-up device connected to each input terminal and a pull-down device connected to each input terminal wherein said pull-down device has a control terminal connected to said CAM output lines.
Advantageously said connecting circuitry further comprises a respective inverter connected between said pull-up/pull-down devices and said input terminals.
Preferably said pull-up device comprises a p FET connected to conduct and said pull-down device comprises plural n FETs, each n FET having a gate connected to a CAM output line.